Introduction

Mathematics often feels like a world of exact answers, but sometimes what really matters is not the whole number itself — it’s the remainder left behind after division.
This idea leads us to one of the simplest and most beautiful concepts in number theory: congruences.

The Idea of “Wrapping Around”

Think of a clock.

A clock has 12 hours.
If it’s 10 o’clock now, what time will it be in 5 hours?

• $10 + 5 = 15$

But clocks don’t show “15”. They wrap around after 12:

• $15$ “wraps around” to $3$.

We say:

• 15 and 3 behave the same on a clock with 12 hours.

This is exactly how congruences work.

The Notation

We write: $$a \equiv b \pmod{n}$$ This means:

• When you divide $a$ by $n$,
• and you divide $b$ by $n$,
• you get the same remainder.

For example:

• $17 \equiv 2 \pmod{5}$
• $22 \equiv 2 \pmod{5}$
• So $17 \equiv 22 \pmod{5}$

All three statements say the same thing:
17 and 22 leave the same remainder when divided by 5.

Thinking in Terms of Remainders

Let’s look at a few examples.

Example 1

$$29 \equiv ? \pmod{7}$$ Divide 29 by 7: $$29 = 7 \times 4 + 1$$ So: $$29 \equiv 1 \pmod{7}$$

Example 2

$$50 \equiv ? \pmod{12}$$ $$50 = 12 \times 4 + 2$$ $$50 \equiv 2 \pmod{12}$$

• This is just like saying: On a 12-hour clock, 50 wraps around to 2.

Remainder vs. Residue

Remainder

A remainder is the number left over after performing ordinary integer division.

• When you divide $a$ by $n$, you get $$a = nq + r$$ where $0 \le r < n$.
• That $r$ is the remainder.
• It is a single, specific number determined by the division algorithm.

Example:
Divide $23$ by $7$:

• $23 = 3\cdot 7 + 2$
• The remainder is 2.

Remainders are about division.

Residue

A residue is a number considered modulo $n$.
It refers to a class of integers that are all congruent to each other.

• Two integers $a$ and $b$ are in the same residue class modulo $n$ if $$a \equiv b \pmod n.$$
• A residue is not a single number — it’s the entire set of integers congruent to each other.

Example:
The residue of $23$ modulo $7$ is the set $$\{ \dots, -12, -5, 2, 9, 16, 23, 30, \dots \}.$$ Residues are about congruence classes.

How they relate

• Every residue class has one remainder in $\{0,1,\dots,n-1\}$.
• But a residue class contains infinitely many integers.

So:

• “Remainder” = one specific representative.
• “Residue” = the whole congruence class.

Calculator

Exercises

1. What is the remainder when 45 is divided by 7? Express this using congruence notation. $$45 \equiv ? \pmod{7}$$

   Solution

   To find the remainder when 45 is divided by 7, we perform the division: $$45 = 7 \times 6 + 3$$ The remainder is 3.

   So, in congruence notation: $$45 \equiv 3 \pmod{7}$$

2. If it's Tuesday today, what day of the week will it be in 100 days? (Consider Sunday as day 0, Monday as day 1, and so on). Express your answer using congruence notation.

   Solution

   The days of the week cycle every 7 days. So, this is a modulo 7 problem.

   If Tuesday is day 2 (Sunday = 0, Monday = 1, Tuesday = 2), we want to find the day 100 days from Tuesday.

   Total days from Sunday (start) = $2 + 100 = 102$

   Now, we find the remainder when 102 is divided by 7: $$102 = 7 \times 14 + 4$$ The remainder is 4.

   Day 4 corresponds to Thursday.

   In congruence notation: $$102 \equiv 4 \pmod{7}$$ Therefore, in 100 days, it will be Thursday.

3. Find the value of $x$ such that: $$-15 \equiv x \pmod{4}$$
   • where $0 \le x < 4$. Express your answer using congruence notation.

   Solution

   We need to find $x$ such that $-15 \equiv x \pmod{4}$, where $0 \le x < 4$.
   To find a positive equivalent for $-15 \pmod{4}$, we can add multiples of 4 to -15 until we get a positive number in the desired range. $$-15 + 4 = -11$$ $$-15 + 4 \times 2 = -15 + 8 = -7$$ $$-15 + 4 \times 3 = -15 + 12 = -3$$ $$-15 + 4 \times 4 = -15 + 16 = 1$$ So, $-15 \equiv 1 \pmod{4}$.

   The value of $x$ is 1.

4. Find the smallest positive integer $y$ such that $5y \equiv 3 \pmod{11}$.

   Solution

   We need to find the smallest positive integer $y$ such that $5y \equiv 3 \pmod{11}$.
   Let's list multiples of 5 modulo 11: $$5 \times 1 = 5 \equiv 5 \pmod{11}$$ $$5 \times 2 = 10 \equiv 10 \pmod{11}$$ $$5 \times 3 = 15 \equiv 4 \pmod{11}$$ $$5 \times 4 = 20 \equiv 9 \pmod{11}$$ $$5 \times 5 = 25 \equiv 3 \pmod{11}$$ $$5 \times 6 = 30 \equiv 8 \pmod{11}$$ $$5 \times 7 = 35 \equiv 2 \pmod{11}$$ $$5 \times 8 = 40 \equiv 7 \pmod{11}$$ $$5 \times 9 = 45 \equiv 1 \pmod{11}$$

   Solving by manually inspecting the multiples

   • We see that when $y = 5$ then $5y \equiv 3 \pmod{11}$
   • So the answer is $5$

   Solving by multiplicative inverse

   • We need to find the multiplicative inverse of 5 modulo 11.
     • This is when $5 \equiv 1 \pmod{11}$
   • So, the multiplicative inverse of 5 modulo 11 is 9, since $5 \times 9 = 45 \equiv 1 \pmod{11}$.

   Now, multiply both sides of the congruence by 9: $$9 \times (5y) \equiv 9 \times 3 \pmod{11}$$ $$45y \equiv 27 \pmod{11}$$ Reduce 45 and 27 modulo 11: $$45 = 4 \times 11 + 1 \implies 45 \equiv 1 \pmod{11}$$ $$27 = 2 \times 11 + 5 \implies 27 \equiv 5 \pmod{11}$$ Substituting these back: $$1y \equiv 5 \pmod{11}$$ $$y \equiv 5 \pmod{11}$$ The smallest positive integer $y$ is 5.

   Check: $5 \times 5 = 25$. $25 = 2 \times 11 + 3$. So $25 \equiv 3 \pmod{11}$. This is correct.

5. Find the remainder when $2^{50}$ is divided by 13. Hint: Consider Fermat's Little Theorem, which states that if $p$ is a prime number, then for any integer $a$ not divisible by $p$, we have $a^{p-1} \equiv 1 \pmod{p}$.

   Solution

   We need to find the remainder when $2^{50}$ is divided by 13.
   Step 1: Identify the properties of the modulus.

   The modulus is $n=13$, which is a prime number.

   Step 2: Apply Fermat's Little Theorem.

   Fermat's Little Theorem states that if $p$ is a prime number, then for any integer $a$ not divisible by $p$, we have $a^{p-1} \equiv 1 \pmod{p}$.

   Here, $a=2$ and $p=13$. Since 13 is prime and 2 is not a multiple of 13, we can apply the theorem: $$2^{13-1} \equiv 2^{12} \equiv 1 \pmod{13}$$ This means that $2^{12}$ leaves a remainder of 1 when divided by 13.

   Step 3: Simplify the exponent.

   We need to find the remainder of $2^{50} \pmod{13}$. We use the fact that $2^{12} \equiv 1 \pmod{13}$ to simplify the exponent 50.

   Divide 50 by 12: $$50 = 12 \times 4 + 2$$ So, we can rewrite $2^{50}$ as: $$2^{50} = 2^{(12 \times 4) + 2} = (2^{12})^4 \times 2^2$$ Step 4: Substitute and calculate.

   Now substitute $2^{12} \equiv 1 \pmod{13}$ into the expression: $$2^{50} \equiv (1)^4 \times 2^2 \pmod{13}$$ $$2^{50} \equiv 1 \times 4 \pmod{13}$$ $$2^{50} \equiv 4 \pmod{13}$$ Step 5: Conclude the remainder.

   Therefore, the remainder when $2^{50}$ is divided by 13 is 4.